The present invention relates to correlators for use in visual signal processing.
Many image processing applications involve simply looking for the presence (or absence) of a known pattern and determining its location. Examples include locating parts on a conveyor belt, verifying the presence of parts during assembly operations, locating bonding pads and alignment marks on semiconductor chips, locating landmarks or targets in aerial imagery, and optical character recognition. Many video signal processing applications involve the computationally related process of convolving a two-dimensional signal array with a mask (e.g., to remove noise or enhance edges).
Both above classes of application require high-speed correlation (or matching) of a mask with an image. In addition, for the image processing examples, it is also necessary to determine the location with the best match. Traditionally, such functions have been implemented in special purpose boards using off-the-shelf components, resulting in large, expensive systems.
An example of how a correlation might be done is shown in FIGS. 1 and 1A. A rectangular image 10 in an image field 12 is captured by a video camera or other means, preprocessed to remove noise of other distortion or enhance edges, etc., and is then presented to a correlator. The image field 12 is represented as a series of binary digits as shown in field 14. Here the zeroes would represent a white background while the ones would represent the dark object.
In the correlation process, image 10 is compared with a series of masks 16, 18, 20, 22, and 24, which are stored in memory as an array of zeroes and ones. The masks have stored different orientations of an ideal image about one axis. The remaining two axes can be matched by moving the image horizontally and vertically, as shown in FIG. 1A. In FIG. 1A, image field 12 with image 10 is being matched against mask 20. As can be seen, the image is first shifted to the right as shown by fields 26, 28, and 30, and then is shifted upward until a best match is obtained. A simple way of determining a match is to compare each digital bit in image field 12 to each digital bit in mask 10 and produce a count of the number of bits which match. This count can then be compared with a threshold value which is chosen for a count which is close enough to indicate a match of the image with the mask. In one alternate method, a small portion of the ideal image could be stored as a mask (such as a 64.times.64 mask for a 128.times.128 image). Portions of the image can then be compared with the mask to determine where a match occurs.
Each line of the digital representation shown in field 14 is referred to as a scan line and the entire field 14 is referred to as a frame. The traditional method of shifting the image as shown in FIG. 1A is to input the digits of a scan line into a series of shift registers and shift the digits to the right sequentially and compare the digits to the mask at each shift position. Such a correlation method is shown in U.S. Pat. No. 4,200,861 to Hubach, et al. As can be seen, this requirement of shifting the bits of an image slows down the processing time due to the requirement for doing a comparison at each shift position.
The processing time required is further increased if one attempts to do gray scale matching. For gray scale matching, rather than each pixel of the image field 12 being either a digital zero or one, each pixel will be a binary number ranging, for instance, from zero to sixteen. Zero could represent white, with sixteen representing black, and the numbers in between representing different shades of grey. Each pixel is then represented by a four bit binary code as illustrated in FIG. 2. The correlation can then be done by comparing bits in a bit plane which consists of a corresponding bit in each of the pixels. The bit planes compared would be first the most significant bit in every pixel, with subsequent comparisons being made of the lesser significant bits. As can be seen, the number of shifts through a shift register required for a correlation is increased by severalfold, with a corresponding increase in processing time.